class Solution:
    def respace(self, dictionary: List[str], sentence: str) -> int:
        if sentence == "": return 0
        if dictionary == []: return len(sentence)
        
        dp = [0] * len(sentence) + [0]
        dictionary.sort(key = lambda x: len(x))
        
        dp[0] = 0 
        
        for i in range(1, len(sentence) + 1):
            dp[i] = dp[i - 1] + 1x
            for j in dictionary:
                if len(j) > i:
                    break
                if sentence[i - len(j): i] == j:
                    dp[i] = min(dp[i], dp[i - len(j)])
        return dp[-1]

